#include "heapsort.h"
#include <iostream>

using std::cout;
using std::endl;

void max_heapify(int a[],int i,int s) {
	int l = left(i);
	int r = right(i);
	int largest = 0;
	if (l<s && a[l]>a[i]) {
		largest = l;
	} 
	else {
		largest = i;
	}
	if (r<s && a[r]>a[largest]) {
		largest = r;
	}
	if (largest!=i) {
		int temp = a[i];
		a[i] = a[largest];
		a[largest] = temp;
		max_heapify(a,largest,s);
	}
}

void build_max_heap(int a[],int s) {
	for (int i=(s-1)/2;i>=0;i--) {
		max_heapify(a,i,s);
	}
}

void heapsort(int a[],int s) {
	build_max_heap(a,s);
	for (int i=s-1;i>0;i--) {
		int temp = a[i];
		a[i] = a[0];
		a[0] = temp;
		s -= 1;
		max_heapify(a,0,s);

	}
}

int heap_maximum(int a[]) {
	return a[0];
}

void heap_increace_key(int *a,int i,int key) {
	if (key<a[i]){
		cout << "new key is not bigger than a[i]" << endl;
	}
	else {
		a[i] = key;
		while (i>0 && a[i]>a[parent(i)]){
			int temp = a[i];
			a[i] = a[parent(i)];
			a[parent(i)] = temp;
			i = parent(i);
		}
	}
}

void print_array(int a[],int s) {
	for (int i=0;i<s;i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}